


<!DOCTYPE html>
<html id="htmlId">
<head>
  <title>Coverage Report > Navigation</title>
  <style type="text/css">
    @import "../../css/coverage.css";
    @import "../../css/highlight-idea.css";
  </style>
  <script type="text/javascript" src="../../js/highlight.pack.js"></script>
</head>

<body>
<div class="content">
<div class="breadCrumbs">
Current scope:     <a href="../../index.html">all classes</a>
    <span class="separator">|</span>
    <a href="../index.html">nl.tudelft.jpacman.npc.ghost</a>
</div>

<h1>Coverage Summary for Class: Navigation (nl.tudelft.jpacman.npc.ghost)</h1>

<table class="coverageStats">

<tr>
  <th class="name">Class</th>
<th class="coverageStat 
">
  Method, %
</th>
<th class="coverageStat 
">
  Line, %
</th>
</tr>
<tr>
  <td class="name">Navigation</td>
<td class="coverageStat">
  <span class="percent">
    0%
  </span>
  <span class="absValue">
    (0/7)
  </span>
</td>
<td class="coverageStat">
  <span class="percent">
    0%
  </span>
  <span class="absValue">
    (0/49)
  </span>
</td>
</tr>
  <tr>
    <td class="name">Navigation$Node</td>
<td class="coverageStat">
  <span class="percent">
    0%
  </span>
  <span class="absValue">
    (0/6)
  </span>
</td>
<td class="coverageStat">
  <span class="percent">
    0%
  </span>
  <span class="absValue">
    (0/13)
  </span>
</td>
  </tr>
<tr>
  <td class="name"><strong>Total</strong></td>
<td class="coverageStat">
  <span class="percent">
    0%
  </span>
  <span class="absValue">
    (0/13)
  </span>
</td>
<td class="coverageStat">
  <span class="percent">
    0%
  </span>
  <span class="absValue">
    (0/62)
  </span>
</td>
</tr>
</table>

<br/>
<br/>


<pre>
<div class="sourceCode" id="sourceCode"><i class="no-highlight">1</i>&nbsp;package nl.tudelft.jpacman.npc.ghost;
<i class="no-highlight">2</i>&nbsp;
<i class="no-highlight">3</i>&nbsp;import java.util.ArrayList;
<i class="no-highlight">4</i>&nbsp;import java.util.HashSet;
<i class="no-highlight">5</i>&nbsp;import java.util.List;
<i class="no-highlight">6</i>&nbsp;import java.util.Set;
<i class="no-highlight">7</i>&nbsp;
<i class="no-highlight">8</i>&nbsp;import nl.tudelft.jpacman.board.Board;
<i class="no-highlight">9</i>&nbsp;import nl.tudelft.jpacman.board.Direction;
<i class="no-highlight">10</i>&nbsp;import nl.tudelft.jpacman.board.Square;
<i class="no-highlight">11</i>&nbsp;import nl.tudelft.jpacman.board.Unit;
<i class="no-highlight">12</i>&nbsp;
<i class="no-highlight">13</i>&nbsp;/**
<i class="no-highlight">14</i>&nbsp; * Navigation provides utility to navigate on {@link Square}s.
<i class="no-highlight">15</i>&nbsp; *
<i class="no-highlight">16</i>&nbsp; * @author Jeroen Roosen 
<i class="no-highlight">17</i>&nbsp; */
<b class="nc"><i class="no-highlight">18</i>&nbsp;public final class Navigation {</b>
<i class="no-highlight">19</i>&nbsp;
<b class="nc"><i class="no-highlight">20</i>&nbsp;    private Navigation() {</b>
<i class="no-highlight">21</i>&nbsp;    }
<i class="no-highlight">22</i>&nbsp;
<i class="no-highlight">23</i>&nbsp;    /**
<i class="no-highlight">24</i>&nbsp;     * Calculates the shortest path. This is done by BFS. This search ensures
<i class="no-highlight">25</i>&nbsp;     * the traveller is allowed to occupy the squares on the way, or returns the
<i class="no-highlight">26</i>&nbsp;     * shortest path to the square regardless of terrain if no traveller is
<i class="no-highlight">27</i>&nbsp;     * specified.
<i class="no-highlight">28</i>&nbsp;     *
<i class="no-highlight">29</i>&nbsp;     * @param from
<i class="no-highlight">30</i>&nbsp;     *            The starting square.
<i class="no-highlight">31</i>&nbsp;     * @param to
<i class="no-highlight">32</i>&nbsp;     *            The destination.
<i class="no-highlight">33</i>&nbsp;     * @param traveller
<i class="no-highlight">34</i>&nbsp;     *            The traveller attempting to reach the destination. If
<i class="no-highlight">35</i>&nbsp;     *            traveller is set to &lt;code&gt;null&lt;/code&gt;, this method will ignore
<i class="no-highlight">36</i>&nbsp;     *            terrain and find the shortest path whether it can actually be
<i class="no-highlight">37</i>&nbsp;     *            reached or not.
<i class="no-highlight">38</i>&nbsp;     * @return The shortest path to the destination or &lt;code&gt;null&lt;/code&gt; if no
<i class="no-highlight">39</i>&nbsp;     *         such path could be found. When the destination is the current
<i class="no-highlight">40</i>&nbsp;     *         square, an empty list is returned.
<i class="no-highlight">41</i>&nbsp;     */
<i class="no-highlight">42</i>&nbsp;    public static List&lt;Direction&gt; shortestPath(Square from, Square to,
<i class="no-highlight">43</i>&nbsp;                                                         Unit traveller) {
<b class="nc"><i class="no-highlight">44</i>&nbsp;        if (from.equals(to)) {</b>
<b class="nc"><i class="no-highlight">45</i>&nbsp;            return new ArrayList&lt;&gt;();</b>
<i class="no-highlight">46</i>&nbsp;        }
<i class="no-highlight">47</i>&nbsp;
<b class="nc"><i class="no-highlight">48</i>&nbsp;        List&lt;Node&gt; targets = new ArrayList&lt;&gt;();</b>
<b class="nc"><i class="no-highlight">49</i>&nbsp;        Set&lt;Square&gt; visited = new HashSet&lt;&gt;();</b>
<b class="nc"><i class="no-highlight">50</i>&nbsp;        targets.add(new Node(null, from, null));</b>
<b class="nc"><i class="no-highlight">51</i>&nbsp;        while (!targets.isEmpty()) {</b>
<b class="nc"><i class="no-highlight">52</i>&nbsp;            Node node = targets.remove(0);</b>
<b class="nc"><i class="no-highlight">53</i>&nbsp;            Square square = node.getSquare();</b>
<b class="nc"><i class="no-highlight">54</i>&nbsp;            if (square.equals(to)) {</b>
<b class="nc"><i class="no-highlight">55</i>&nbsp;                return node.getPath();</b>
<i class="no-highlight">56</i>&nbsp;            }
<b class="nc"><i class="no-highlight">57</i>&nbsp;            visited.add(square);</b>
<b class="nc"><i class="no-highlight">58</i>&nbsp;            addNewTargets(traveller, targets, visited, node, square);</b>
<b class="nc"><i class="no-highlight">59</i>&nbsp;        }</b>
<b class="nc"><i class="no-highlight">60</i>&nbsp;        return null;</b>
<i class="no-highlight">61</i>&nbsp;    }
<i class="no-highlight">62</i>&nbsp;
<i class="no-highlight">63</i>&nbsp;    private static void addNewTargets(Unit traveller, List&lt;Node&gt; targets,
<i class="no-highlight">64</i>&nbsp;                                      Set&lt;Square&gt; visited, Node node, Square square) {
<b class="nc"><i class="no-highlight">65</i>&nbsp;        for (Direction direction : Direction.values()) {</b>
<b class="nc"><i class="no-highlight">66</i>&nbsp;            Square target = square.getSquareAt(direction);</b>
<b class="nc"><i class="no-highlight">67</i>&nbsp;            if (!visited.contains(target)</b>
<b class="nc"><i class="no-highlight">68</i>&nbsp;                &amp;&amp; (traveller == null || target.isAccessibleTo(traveller))) {</b>
<b class="nc"><i class="no-highlight">69</i>&nbsp;                targets.add(new Node(direction, target, node));</b>
<i class="no-highlight">70</i>&nbsp;            }
<i class="no-highlight">71</i>&nbsp;        }
<i class="no-highlight">72</i>&nbsp;    }
<i class="no-highlight">73</i>&nbsp;
<i class="no-highlight">74</i>&nbsp;    /**
<i class="no-highlight">75</i>&nbsp;     * Finds the nearest unit of the given type and returns its location. This
<i class="no-highlight">76</i>&nbsp;     * method will perform a breadth first search starting from the given
<i class="no-highlight">77</i>&nbsp;     * square.
<i class="no-highlight">78</i>&nbsp;     *
<i class="no-highlight">79</i>&nbsp;     * @param type
<i class="no-highlight">80</i>&nbsp;     *            The type of unit to search for.
<i class="no-highlight">81</i>&nbsp;     * @param currentLocation
<i class="no-highlight">82</i>&nbsp;     *            The starting location for the search.
<i class="no-highlight">83</i>&nbsp;     * @return The nearest unit of the given type, or &lt;code&gt;null&lt;/code&gt; if no
<i class="no-highlight">84</i>&nbsp;     *         such unit could be found.
<i class="no-highlight">85</i>&nbsp;     */
<i class="no-highlight">86</i>&nbsp;    public static Unit findNearest(Class&lt;? extends Unit&gt; type,
<i class="no-highlight">87</i>&nbsp;                                             Square currentLocation) {
<b class="nc"><i class="no-highlight">88</i>&nbsp;        List&lt;Square&gt; toDo = new ArrayList&lt;&gt;();</b>
<b class="nc"><i class="no-highlight">89</i>&nbsp;        Set&lt;Square&gt; visited = new HashSet&lt;&gt;();</b>
<i class="no-highlight">90</i>&nbsp;
<b class="nc"><i class="no-highlight">91</i>&nbsp;        toDo.add(currentLocation);</b>
<i class="no-highlight">92</i>&nbsp;
<b class="nc"><i class="no-highlight">93</i>&nbsp;        while (!toDo.isEmpty()) {</b>
<b class="nc"><i class="no-highlight">94</i>&nbsp;            Square square = toDo.remove(0);</b>
<b class="nc"><i class="no-highlight">95</i>&nbsp;            Unit unit = findUnit(type, square);</b>
<b class="nc"><i class="no-highlight">96</i>&nbsp;            if (unit != null) {</b>
<b class="nc"><i class="no-highlight">97</i>&nbsp;                assert unit.hasSquare();</b>
<b class="nc"><i class="no-highlight">98</i>&nbsp;                return unit;</b>
<i class="no-highlight">99</i>&nbsp;            }
<b class="nc"><i class="no-highlight">100</i>&nbsp;            visited.add(square);</b>
<b class="nc"><i class="no-highlight">101</i>&nbsp;            for (Direction direction : Direction.values()) {</b>
<b class="nc"><i class="no-highlight">102</i>&nbsp;                Square newTarget = square.getSquareAt(direction);</b>
<b class="nc"><i class="no-highlight">103</i>&nbsp;                if (!visited.contains(newTarget) &amp;&amp; !toDo.contains(newTarget)) {</b>
<b class="nc"><i class="no-highlight">104</i>&nbsp;                    toDo.add(newTarget);</b>
<i class="no-highlight">105</i>&nbsp;                }
<i class="no-highlight">106</i>&nbsp;            }
<b class="nc"><i class="no-highlight">107</i>&nbsp;        }</b>
<b class="nc"><i class="no-highlight">108</i>&nbsp;        return null;</b>
<i class="no-highlight">109</i>&nbsp;    }
<i class="no-highlight">110</i>&nbsp;
<i class="no-highlight">111</i>&nbsp;    /**
<i class="no-highlight">112</i>&nbsp;     *  Finds a subtype of Unit in a level.
<i class="no-highlight">113</i>&nbsp;     *  This method is very useful for finding the ghosts in the parsed map.
<i class="no-highlight">114</i>&nbsp;     *
<i class="no-highlight">115</i>&nbsp;     * @param clazz the type to search for.
<i class="no-highlight">116</i>&nbsp;     * @param board the board to find the unit in.
<i class="no-highlight">117</i>&nbsp;     * @param &lt;T&gt; the return type, same as the type in clazz.
<i class="no-highlight">118</i>&nbsp;     *
<i class="no-highlight">119</i>&nbsp;     * @return the first unit found of type clazz, or null.
<i class="no-highlight">120</i>&nbsp;     */
<i class="no-highlight">121</i>&nbsp;    public static &lt;T extends Unit&gt; T findUnitInBoard(Class&lt;T&gt; clazz, Board board) {
<b class="nc"><i class="no-highlight">122</i>&nbsp;        for (int y = 0; y &lt; board.getHeight(); y++) {</b>
<b class="nc"><i class="no-highlight">123</i>&nbsp;            for (int x = 0; x &lt; board.getWidth(); x++) {</b>
<b class="nc"><i class="no-highlight">124</i>&nbsp;                final T ghost = Navigation.findUnit(clazz, board.squareAt(x, y));</b>
<b class="nc"><i class="no-highlight">125</i>&nbsp;                if (ghost != null) {</b>
<b class="nc"><i class="no-highlight">126</i>&nbsp;                    return ghost;</b>
<i class="no-highlight">127</i>&nbsp;                }
<i class="no-highlight">128</i>&nbsp;            }
<i class="no-highlight">129</i>&nbsp;        }
<i class="no-highlight">130</i>&nbsp;
<b class="nc"><i class="no-highlight">131</i>&nbsp;        return null;</b>
<i class="no-highlight">132</i>&nbsp;    }
<i class="no-highlight">133</i>&nbsp;
<i class="no-highlight">134</i>&nbsp;    /**
<i class="no-highlight">135</i>&nbsp;     * Determines whether a square has an occupant of a certain type.
<i class="no-highlight">136</i>&nbsp;     *
<i class="no-highlight">137</i>&nbsp;     * @param type
<i class="no-highlight">138</i>&nbsp;     *            The type to search for.
<i class="no-highlight">139</i>&nbsp;     * @param square
<i class="no-highlight">140</i>&nbsp;     *            The square to search.
<i class="no-highlight">141</i>&nbsp;     * @param &lt;T&gt;
<i class="no-highlight">142</i>&nbsp;     *           the type of unit we searched for.
<i class="no-highlight">143</i>&nbsp;     *
<i class="no-highlight">144</i>&nbsp;     * @return A unit of type T, iff such a unit occupies this square, or
<i class="no-highlight">145</i>&nbsp;     *         &lt;code&gt;null&lt;/code&gt; of none does.
<i class="no-highlight">146</i>&nbsp;     */
<i class="no-highlight">147</i>&nbsp;    @SuppressWarnings(&quot;unchecked&quot;)
<i class="no-highlight">148</i>&nbsp;    public static &lt;T extends Unit&gt; T findUnit(Class&lt;T&gt; type, Square square) {
<b class="nc"><i class="no-highlight">149</i>&nbsp;        for (Unit unit : square.getOccupants()) {</b>
<b class="nc"><i class="no-highlight">150</i>&nbsp;            if (type.isInstance(unit)) {</b>
<b class="nc"><i class="no-highlight">151</i>&nbsp;                assert unit.hasSquare();</b>
<b class="nc"><i class="no-highlight">152</i>&nbsp;                return (T) unit;</b>
<i class="no-highlight">153</i>&nbsp;            }
<b class="nc"><i class="no-highlight">154</i>&nbsp;        }</b>
<b class="nc"><i class="no-highlight">155</i>&nbsp;        return null;</b>
<i class="no-highlight">156</i>&nbsp;    }
<i class="no-highlight">157</i>&nbsp;
<i class="no-highlight">158</i>&nbsp;    /**
<i class="no-highlight">159</i>&nbsp;     * Helper class to keep track of the path.
<i class="no-highlight">160</i>&nbsp;     *
<i class="no-highlight">161</i>&nbsp;     * @author Jeroen Roosen
<i class="no-highlight">162</i>&nbsp;     */
<b class="nc"><i class="no-highlight">163</i>&nbsp;    private static final class Node {</b>
<i class="no-highlight">164</i>&nbsp;
<i class="no-highlight">165</i>&nbsp;        /**
<i class="no-highlight">166</i>&nbsp;         * The direction for this node, which is &lt;code&gt;null&lt;/code&gt; for the root
<i class="no-highlight">167</i>&nbsp;         * node.
<i class="no-highlight">168</i>&nbsp;         */
<i class="no-highlight">169</i>&nbsp;        private final Direction direction;
<i class="no-highlight">170</i>&nbsp;
<i class="no-highlight">171</i>&nbsp;        /**
<i class="no-highlight">172</i>&nbsp;         * The parent node, which is &lt;code&gt;null&lt;/code&gt; for the root node.
<i class="no-highlight">173</i>&nbsp;         */
<i class="no-highlight">174</i>&nbsp;        private final Node parent;
<i class="no-highlight">175</i>&nbsp;
<i class="no-highlight">176</i>&nbsp;        /**
<i class="no-highlight">177</i>&nbsp;         * The square associated with this node.
<i class="no-highlight">178</i>&nbsp;         */
<i class="no-highlight">179</i>&nbsp;        private final Square square;
<i class="no-highlight">180</i>&nbsp;
<i class="no-highlight">181</i>&nbsp;        /**
<i class="no-highlight">182</i>&nbsp;         * Creates a new node.
<i class="no-highlight">183</i>&nbsp;         *
<i class="no-highlight">184</i>&nbsp;         * @param direction
<i class="no-highlight">185</i>&nbsp;         *            The direction, which is &lt;code&gt;null&lt;/code&gt; for the root
<i class="no-highlight">186</i>&nbsp;         *            node.
<i class="no-highlight">187</i>&nbsp;         * @param square
<i class="no-highlight">188</i>&nbsp;         *            The square.
<i class="no-highlight">189</i>&nbsp;         * @param parent
<i class="no-highlight">190</i>&nbsp;         *            The parent node, which is &lt;code&gt;null&lt;/code&gt; for the root
<i class="no-highlight">191</i>&nbsp;         *            node.
<i class="no-highlight">192</i>&nbsp;         */
<b class="nc"><i class="no-highlight">193</i>&nbsp;        Node(Direction direction, Square square, Node parent) {</b>
<b class="nc"><i class="no-highlight">194</i>&nbsp;            this.direction = direction;</b>
<b class="nc"><i class="no-highlight">195</i>&nbsp;            this.square = square;</b>
<b class="nc"><i class="no-highlight">196</i>&nbsp;            this.parent = parent;</b>
<i class="no-highlight">197</i>&nbsp;        }
<i class="no-highlight">198</i>&nbsp;
<i class="no-highlight">199</i>&nbsp;        /**
<i class="no-highlight">200</i>&nbsp;         * @return The direction for this node, or &lt;code&gt;null&lt;/code&gt; if this
<i class="no-highlight">201</i>&nbsp;         *         node is a root node.
<i class="no-highlight">202</i>&nbsp;         */
<i class="no-highlight">203</i>&nbsp;        private Direction getDirection() {
<b class="nc"><i class="no-highlight">204</i>&nbsp;            return direction;</b>
<i class="no-highlight">205</i>&nbsp;        }
<i class="no-highlight">206</i>&nbsp;
<i class="no-highlight">207</i>&nbsp;        /**
<i class="no-highlight">208</i>&nbsp;         * @return The square for this node.
<i class="no-highlight">209</i>&nbsp;         */
<i class="no-highlight">210</i>&nbsp;        private Square getSquare() {
<b class="nc"><i class="no-highlight">211</i>&nbsp;            return square;</b>
<i class="no-highlight">212</i>&nbsp;        }
<i class="no-highlight">213</i>&nbsp;
<i class="no-highlight">214</i>&nbsp;        /**
<i class="no-highlight">215</i>&nbsp;         * @return The parent node, or &lt;code&gt;null&lt;/code&gt; if this node is a root
<i class="no-highlight">216</i>&nbsp;         *         node.
<i class="no-highlight">217</i>&nbsp;         */
<i class="no-highlight">218</i>&nbsp;        private Node getParent() {
<b class="nc"><i class="no-highlight">219</i>&nbsp;            return parent;</b>
<i class="no-highlight">220</i>&nbsp;        }
<i class="no-highlight">221</i>&nbsp;
<i class="no-highlight">222</i>&nbsp;        /**
<i class="no-highlight">223</i>&nbsp;         * Returns the list of values from the root of the tree to this node.
<i class="no-highlight">224</i>&nbsp;         *
<i class="no-highlight">225</i>&nbsp;         * @return The list of values from the root of the tree to this node.
<i class="no-highlight">226</i>&nbsp;         */
<i class="no-highlight">227</i>&nbsp;        private List&lt;Direction&gt; getPath() {
<b class="nc"><i class="no-highlight">228</i>&nbsp;            if (parent == null) {</b>
<b class="nc"><i class="no-highlight">229</i>&nbsp;                return new ArrayList&lt;&gt;();</b>
<i class="no-highlight">230</i>&nbsp;            }
<b class="nc"><i class="no-highlight">231</i>&nbsp;            List&lt;Direction&gt; path = parent.getPath();</b>
<b class="nc"><i class="no-highlight">232</i>&nbsp;            path.add(getDirection());</b>
<b class="nc"><i class="no-highlight">233</i>&nbsp;            return path;</b>
<i class="no-highlight">234</i>&nbsp;        }
<i class="no-highlight">235</i>&nbsp;    }
<i class="no-highlight">236</i>&nbsp;}
</div>
</pre>
</div>

<script type="text/javascript">
(function() {
    var msie = false, msie9 = false;
    /*@cc_on
      msie = true;
      @if (@_jscript_version >= 9)
        msie9 = true;
      @end
    @*/

    if (!msie || msie && msie9) {
        var codeBlock = document.getElementById('sourceCode');

        if (codeBlock) {
            hljs.highlightBlock(codeBlock);
        }
    }
})();
</script>

<div class="footer">
    
    <div style="float:right;">generated on 2022-05-22 18:55</div>
</div>
</body>
</html>
